package _08_堆;

import _05_树.printer.BinaryTreeInfo;

import java.util.Comparator;

/*
    二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆
    最大堆:任意节点的值都大于他的左右子节点 最大值在根节点
    底层由数组存储元素，元素存放按照索引从上到下，从左到右
 */
public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo{
    private E[] elements; //内部由数组存储元素
    private static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap(E[] elements){
        this(elements,null);
    }

    public BinaryHeap(E[] elements,Comparator<E> comparator){
        super(comparator);
        if(elements == null || elements.length == 0){
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        }else{
            //对数组进行深拷贝
            size = elements.length;
            int capacity = Math.max(elements.length,DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for(int i=0;i< elements.length;++i){
                this.elements[i] = elements[i];
            }
            heapify(); //开始批量建堆
        }
    }

    public BinaryHeap(){
        this(null,null);
    }

    public BinaryHeap(Comparator<E> comparator){
        this(null,comparator);
    }

    /**
     * 批量建堆
     */
    private void heapify(){
        //自上而下的上滤,从根节点的下一个节点开始,每个都跟父节点进行比较
        //效率较差
        /*for(int i=1;i<size;++i){
            siftUp(i);
        }*/

        //自下而上的下滤，从最后一个非叶子节点，不断地跟子节点比较
        for(int i=(size >> 1)-1;i>=0;--i){
            siftDown(i);
        }
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 添加元素到数组尾部，再通过上滤操作，修复二叉堆的性质
     * @param element
     */
    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size+1);
        elements[size++] = element; //添加到数组尾部
        siftUp(size-1); //上滤
    }

    /**
     * 传入一个索引，将该索引的元素和不断的和父节点相比，只要比父节点小就停止，否则就一直交换
     * @param index
     */
    private void siftUp(int index){
        E element = elements[index]; //目标元素
        while(index>0){ //去除根节点
            int parentIndex = (index - 1) >> 1; //父节点的索引是 i-1 / 2
            E parentElement = elements[parentIndex];

            if(compare(element,parentElement) <=0) break; //当前元素比父节点小或者等于

            //将父节点放入index处
            elements[index] = parentElement;
            index = parentIndex; //重新设置index,进行下一轮的比较
        }
        elements[index] = element; //退出循环后，将目标位置放入index即可
    }

    /**
     * 获取堆顶元素
     * @return
     */
    @Override
    public E get() {
        emptyCheck(); //安全检查
        return elements[0];
    }

    /**
     * 删除堆顶元素并返回
     * 逻辑:将最后一个元素覆盖堆顶元素，删除最后一个元素，在对覆盖的堆顶元素进行下滤，维护最大堆的性质
     * @return 返回堆顶元素
     */
    @Override
    public E remove() {
        emptyCheck();
        int lastIndex = --size;
        E top = elements[0]; //返回堆顶元素
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null; //清空最后一个元素
        siftDown(0); //对覆盖的堆顶元素进行下滤
        return top;
    }

    /**
     * 对给定索引位置的元素进下滤
     * 让父节点跟左右子节点最大的进行比较，如果父节点比他小就交换，直到父节点>=它
     * @param index
     */
    private void siftDown(int index){
        E element = elements[index]; //目标元素
        //判断是否有子节点，规律:第一个叶子节点的索引 = 非叶子节点的总数
        // 完全二叉树中非叶子节点的总数: floor(总结点个数/2)
        int noLeaf = size >> 1; //拿到非叶子节点的总数，也就是第一个叶子节点的索引
        //必须保证index是非叶子节点，也就是小于第一个叶子节点的索引,那么它就有子节点，可以进行比较，下滤
        while(index<noLeaf){
            //完全二叉树的子节点情况
            //1.只有左子节点，无右子节点
            //2.左右子节点都有

            //先取左子节点的索引
            int leftChildIndex = (index << 1) + 1;
            E leftChildElement = elements[leftChildIndex];

            //再取右子节点的索引
            int rightChildIndex = leftChildIndex + 1;

            //先判断右子节点是否存在，在比较左右子节点，拿出最大的一个
            if(rightChildIndex < size && compare(elements[rightChildIndex],leftChildElement)>0){
                //右边比左边大，将右边的索引赋值给左边，
                leftChildElement = elements[leftChildIndex = rightChildIndex];
            }

            if(compare(element,leftChildElement)>=0) break; //父节点比左子节点大 就不用下滤

            elements[index] = leftChildElement; //大的放上去
            index = leftChildIndex; //更新index的值
        }
        elements[index] = element; //最后将element放入找到的位置

    }

    /**
     * 删除堆顶元素并返回，在添加一个新元素
     * 逻辑:如果有元素,那就直接将待添加的元素放入堆顶，然后对堆顶元素进行下滤
     * 如果没有元素，默认添加到第一个即可
     * @param element
     * @return
     */
    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        E root = null;
        if(size == 0){ //堆中没有元素
            elements[0] = element;
            size++;
        }else{
            root = elements[0];
            elements[0] = element;
            siftDown(0); //对0进行下滤
        }
        return root;
    }

    //扩容方法
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if(capacity <= oldCapacity) return;

        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];

        for(int i=0;i<size;++i){
            newElements[i] = elements[i];
        }

        elements = newElements;

        System.out.println(oldCapacity+"扩容为:"+newCapacity);
    }

    /**
     * 检查堆是否为空
     */
    private void emptyCheck(){
        if(size == 0){
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }

    /**
     * 检测传入的元素是否为空，元素必须具备可比较性，所以不能为空
     * @param element
     */
    private void elementNotNullCheck(E element){
        if(element == null){
            throw new IllegalArgumentException("element must not be null");
        }
    }

    @Override
    public Object root() {
        return 0;
    }

    //返回左子节点
    @Override
    public Object left(Object node) {
        Integer index = (Integer)node;
        index = (index << 1) + 1;
        return index >= size ? null : index;
    }

    //返回右子节点
    @Override
    public Object right(Object node) {
        Integer index = (Integer)node;
        index = (index << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        Integer index = (Integer)node;
        return elements[index];
    }
}
